package bin_tree.heap.leetcode;

import java.util.*;

/**
 * 出现频率最高的前k个单词，若频率相同，按照字典序排序
 * 输出结果时，按照频率由高到低来输出结果
 */
public class Num692_TopKFreq {
    public List<String> topKFrequent(String[] words, int k) {
        // 1.用Map来保存每个单词以及其出现的频次
        Map<String,Integer> wordsTable = new HashMap<>();
        for (String str : words) {
            if (wordsTable.containsKey(str)) {
                int times = wordsTable.get(str);
                wordsTable.put(str,times + 1);
            }else {
                wordsTable.put(str,1);
            }
        }
        // 此时wordsTable保存了每个不重复的单词以及其出现的频次
        // 取大用小
        Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 先按照出现频次来判定
                int o1Times = wordsTable.get(o1);
                int o2Times = wordsTable.get(o2);
                // 频次相同按照字典序排序
                // 由于最终使用头插法，此时的字典序和ASCII"反"着来
                return o1Times == o2Times ? o2.compareTo(o1) : o1Times - o2Times;
            }
        });
        // 2.扫描Map集合，保存出现频次最高的前k个单词
        for (Map.Entry<String,Integer> entry : wordsTable.entrySet()) {
            queue.offer(entry.getKey());
            if (queue.size() > k) {
                queue.poll();
            }
        }
        // 3.此时优先级队列中就保存了出现频次最高的前k个单词，进行输出保存
        LinkedList<String> result = new LinkedList<>();
        while (!queue.isEmpty()) {
            // 现在是小堆，出队时按照出现频次由低到高进行出队
            // 要实现从高到低的保存，使用头插法来保存元素~
            result.addFirst(queue.poll());
        }
        return result;
    }
}
